Một bảng chữ cái xếp hạng là một cặp bảng chữ cái F {\displaystyle {\mathcal {F}}} và hàm bậc (arity) sao cho có thể xây dựng một số hạng. Các thành tố trống (bậc bằng không) còn được gọi là hằng. Toán hạng được xây dựng bằng các ký hiện bậc một và hằng có thể được coi là xâu. Bậc cao hơn tạo ra cây.

Một ôtômat cây hữu hạn trên F {\displaystyle F} được định nghĩa là: ( Q , F , Q f , Δ ) {\displaystyle (Q,F,Q_{f},\Delta )}

Ở đây, Q {\displaystyle Q} là tập các trạng thái, F {\displaystyle F} là một bảng chữ cái xếp hạng Q f ⊆ Q {\displaystyle Q_{f}\subseteq Q} là một tập các trạng thái kết thúc và Δ {\displaystyle \Delta } là tập luật chuyển trạng thái, nghĩa là các luật viết lại một nút có các con là trạng thái thành nút trạng thái mới.

Không có trạng thái bắt đầu nhưng các luật chuyển cho ký hiệu hằng (nút lá) có thể được coi là các luật bắt đầu. Cây được chấp nhận nếu trạng thái ở gốc là một trạng thái chấp nhận.

Một ôtômat hữu hạn trên xuống trên F {\displaystyle F} được định nghĩa bởi: ( Q , F , I , Δ ) {\displaystyle (Q,F,I,\Delta )}

Có hai điểm khác biệt với ôtômat cây dưới lên: thứ nhất, I ⊆ Q {\displaystyle I\subseteq Q} , tập trạng thái đầu thay cho Q F {\displaystyle Q_{F}} ; thứ hai, các luật chuyển đi theo chiều ngược lại, nghĩa là viết lại một nút trạng thái thành nút với các nút con là trạng thái. Cây được chấp nhận nếu mọi nhánh đều được duyệt qua theo cách này.

Các luật viết lại khiến các ký hiệu của Q {\displaystyle Q} 'di chuyển' dọc theo các nhánh của cây.